#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

class Interval {
public:
    Interval(int a, int b): start(a), end(b) {}
    int start;
    int end;
};


void  mergeInterval(vector<Interval> &A, int start, int end)
{
    int leftIndex = -1, rightIndex = -1, lo, hi;
    if (A.empty()) {A.push_back(Interval(start, end));return;}
    else if (A[A.size()-1].end <start) {A.push_back(Interval(start, end)); return;}
    else if (A[0].start > end) {A.insert(A.begin(), Interval(start, end)); return;}

    //find the left insert point
    lo = 0;
    hi = A.size() -1;
    int target = start;
    while (lo < hi) {
        int mid = lo + (hi-lo)/2;
        if (A[mid].end <= target && A[mid+1].end >= target) {
            leftIndex = mid;
            break;
        } else if (A[mid].end > target) {
            hi = mid;
        } else {
           lo = mid+1;
        }
    }
	int leftErase;
	if (leftIndex != -1) {
        if (A[leftIndex].end <start) {
            leftErase = leftIndex+1;
        } else {
            leftErase = leftIndex;
        }
        start = min(A[leftErase].start, start);
    } else {
        leftErase = 0;
        start = min(A[0].start, start);
	}

    //find the right insert point
    lo = 0;
    hi = A.size() -1;
    target = end;
    while (lo < hi) {
        int mid = lo + (hi-lo)/2;
        if (A[mid].start <= target && A[mid+1].start >= target) {
            rightIndex = mid;
            break;
        } else if (A[mid].start > target) {
            hi = mid;
        } else {
           lo = mid+1;
        }
    }

	int rightErase;
	if (rightIndex != -1) {
		if (A[rightIndex+1].start > end) {
			rightErase = rightIndex;
		}else {
			rightErase = rightIndex + 1;
		}
		end = max(A[rightErase].end, end);
	} else {
		rightErase = A.size()-1;
		end = max(A[A.size()-1].end, end);
	}

	A.erase(A.begin()+leftErase, A.begin()+rightErase+1);
	A.insert(A.begin()+leftErase, Interval(start, end));

    cout << " -------Dummping out Interval ------- " << endl;
    for (int i = 0; i < A.size(); i++)
        cout << A[i].start << " " << A[i].end << endl;
}

int main(int argc, char **argv)
{
    vector<Interval> myInterval;

    cout << "-----------------Test 1--------------------" << endl;
    mergeInterval(myInterval, 4, 10);
    mergeInterval(myInterval, 11, 12);
    mergeInterval(myInterval, 17, 20);
    mergeInterval(myInterval, 22, 28);
    mergeInterval(myInterval, 1, 3);
    mergeInterval(myInterval, 32, 40);
    for (int i = 0; i < myInterval.size(); i++) {
        cout << myInterval[i].start << " " << myInterval[i].end << endl;
    }
    cout << "------------------------" << endl;
    mergeInterval(myInterval, 18, 25);
	mergeInterval(myInterval, 12, 33);
	mergeInterval(myInterval, 0, 50);


    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
